#include <string>
#include <vector>
#include <iostream>
using namespace std;
/*
判断一个字符串的括号匹配
(){} / {[]} / [{}]
{[}]} / { / ({)}

{[]} 
    ^

vector<char> store; // 存储当前已经读到过的字符

如果读到的是各种左括号，就把它放到 store 里

当我们读到一个右括号的时候，它必须和 store 里的最后一个括号匹配。

如果匹配，继续往后读

如果不匹配，return false;
*/

bool is_valid_parenteses(string s)
{
  vector<char> store;
  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] == '(' || s[i] == '[' || s[i] == '{')
    {
      store.push_back(s[i]);
    }
    if (s[i] == ')')
    {
      if (store.size() == 0)
      {
        return false;
      }
      if (store.back() != '(')
      {
        return false;
      }
      store.pop_back();
    }
    if (s[i] == ']')
    {
      if (store.size() == 0)
      {
        return false;
      }
      if (store.back() != '[')
      {
        return false;
      }
      store.pop_back();
    }
    if (s[i] == '}')
    {
      if (store.size() == 0)
      {
        return false;
      }
      if (store.back() != '{')
      {
        return false;
      }
      store.pop_back();  
    }
  }
  return true;
}

int main(int argc, char const *argv[])
{
  string s1 {"()[]{}"};
  string s2 {"([{}])"};
  string s3 {"}{"};
  string s4 {"(}["};
  cout << is_valid_parenteses(s3) << endl;
  return 0;
}
